B3645 数列前缀和 2 - 洛谷

B3645 数列前缀和 2 - 洛谷
 B 3645 数列前缀和2 题解 - lrqlrq250 的博客 - 洛谷博客

常用的 $L A T E X$ 公式

![](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Z-attachment/Pasted image 20231127154615.png)

$\prod_{i = l}^{r} a_{i} (\mod p)$ 发现等价于 $\frac{\prod_{i = 1}^{r} a_{i}}{\prod_{i = 1}^{l - 1} a_{i}}$

则答案为 $\prod_{i = 1}^{r} a_{i} \times i n v [\prod_{i = 1}^{l - 1} a_{i}]$ , $i n v [i]$ 为 $i$ 在 $\mod p$ 意义下的乘法逆元

即为 $s [r] \times i n v [s [l - 1]]$ ,
$∴$ $a n s \oplus = s [r] \times i n v [s [l - 1]]$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll p = 1145141;
int n, q;
ll a[1000010],inv[1200010],s[1000010];
int main()
{
    ios::sync_with_stdio(0), cin.tie(nullptr);
    s[0] = inv[1] = 1;
    cin >>n >> q;
    for (int i = 1; i <= n;i++) cin >> a[i];
    for (int i = 1; i <= n;i++) s[i] = s[i - 1] * a[i] % p;//前缀积s[i]
    for (int i = 2; i <= p; i++)//到p，不是到n!!！
        inv[i] = (p - p / i) * inv[p % i] % p;
    ll ans = 0;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        ans ^= s[r] * inv[s[l-1]] % p;
    }
    cout << ans << '\n';
}